Single-machine scheduling

Single-machine scheduling or single-resource scheduling is the process of assigning a group of tasks to a single machine or resource. The tasks are arranged so that one or many performance measures may be optimized.

1 Performance measures
2 Solution techniques
- 2.1 Heuristics
- 2.2 Computational

Performance measures

The performance measures of the tasks in the single machine scheduling problem include:

Tardiness – $max(0, receipt\;date - due\;date)$
Earliness – $max(0, due\;date - receipt\;date)$
Lateness – $receipt\;date - due\;date$
Flowtime – $end\;date - start\;date$

Solution techniques

Many solution techniques have been applied to solving single machine scheduling problems. Some of them are listed below.

Heuristics

Shortest processing time (SPT)

The SPT schedule is optimal if the objective is to minimize the average flowtime.

Earliest due date (EDD)

The EDD schedule is optimal if the objective is to minimize the maximum lateness.

Computational

Genetic algorithms
Neural networks
Simulated annealing
Ant colonies

Single-machine scheduling

Contents

Performance measures

Solution techniques

Heuristics

Computational